{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reward Top K Students"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: topStudents"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #奖励最顶尖的 K 名学生"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个字符串数组&nbsp;<code>positive_feedback</code> 和&nbsp;<code>negative_feedback</code>&nbsp;，分别包含表示正面的和负面的词汇。<strong>不会</strong>&nbsp;有单词同时是正面的和负面的。</p>\n",
    "\n",
    "<p>一开始，每位学生分数为&nbsp;<code>0</code>&nbsp;。每个正面的单词会给学生的分数 <strong>加&nbsp;</strong><code>3</code>&nbsp;分，每个负面的词会给学生的分数 <strong>减&nbsp;</strong>&nbsp;<code>1</code>&nbsp;分。</p>\n",
    "\n",
    "<p>给你&nbsp;<code>n</code>&nbsp;个学生的评语，用一个下标从 <strong>0</strong>&nbsp;开始的字符串数组&nbsp;<code>report</code>&nbsp;和一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>student_id</code>&nbsp;表示，其中&nbsp;<code>student_id[i]</code>&nbsp;表示这名学生的 ID ，这名学生的评语是&nbsp;<code>report[i]</code>&nbsp;。每名学生的 ID <strong>互不相同</strong>。</p>\n",
    "\n",
    "<p>给你一个整数&nbsp;<code>k</code>&nbsp;，请你返回按照得分&nbsp;<strong>从高到低</strong>&nbsp;最顶尖的<em>&nbsp;</em><code>k</code>&nbsp;名学生。如果有多名学生分数相同，ID 越小排名越前。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>positive_feedback = [\"smart\",\"brilliant\",\"studious\"], negative_feedback = [\"not\"], report = [\"this student is studious\",\"the student is smart\"], student_id = [1,2], k = 2\n",
    "<b>输出：</b>[1,2]\n",
    "<b>解释：</b>\n",
    "两名学生都有 1 个正面词汇，都得到 3 分，学生 1 的 ID 更小所以排名更前。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>positive_feedback = [\"smart\",\"brilliant\",\"studious\"], negative_feedback = [\"not\"], report = [\"this student is not studious\",\"the student is smart\"], student_id = [1,2], k = 2\n",
    "<b>输出：</b>[2,1]\n",
    "<b>解释：</b>\n",
    "- ID 为 1 的学生有 1 个正面词汇和 1 个负面词汇，所以得分为 3-1=2 分。\n",
    "- ID 为 2 的学生有 1 个正面词汇，得分为 3 分。\n",
    "学生 2 分数更高，所以返回 [2,1] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= positive_feedback.length, negative_feedback.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= positive_feedback[i].length, negative_feedback[j].length &lt;= 100</code></li>\n",
    "\t<li><code>positive_feedback[i]</code> 和&nbsp;<code>negative_feedback[j]</code>&nbsp;都只包含小写英文字母。</li>\n",
    "\t<li><code>positive_feedback</code> 和&nbsp;<code>negative_feedback</code>&nbsp;中不会有相同单词。</li>\n",
    "\t<li><code>n == report.length == student_id.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>report[i]</code>&nbsp;只包含小写英文字母和空格&nbsp;<code>' '</code>&nbsp;。</li>\n",
    "\t<li><code>report[i]</code>&nbsp;中连续单词之间有单个空格隔开。</li>\n",
    "\t<li><code>1 &lt;= report[i].length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= student_id[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>student_id[i]</code>&nbsp;的值 <strong>互不相同</strong>&nbsp;。</li>\n",
    "\t<li><code>1 &lt;= k &lt;= n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reward-top-k-students](https://leetcode.cn/problems/reward-top-k-students/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reward-top-k-students](https://leetcode.cn/problems/reward-top-k-students/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"smart\",\"brilliant\",\"studious\"]\\n[\"not\"]\\n[\"this student is studious\",\"the student is smart\"]\\n[1,2]\\n2', '[\"smart\",\"brilliant\",\"studious\"]\\n[\"not\"]\\n[\"this student is not studious\",\"the student is smart\"]\\n[1,2]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        positive_feedback = set(positive_feedback)\n",
    "        negative_feedback = set(negative_feedback)\n",
    "        for i,rp in enumerate(report):\n",
    "            rp = rp.split(\" \")\n",
    "            score = 0\n",
    "            for w in rp:\n",
    "                if w in positive_feedback:\n",
    "                    score+=3\n",
    "                elif w in negative_feedback:\n",
    "                    score-=1\n",
    "            report[i] = score\n",
    "        # print(report)\n",
    "        haha = [(-report[i],student_id[i]) for i in range(len(report))]\n",
    "        haha.sort()\n",
    "        return list(haha[i][1] for i in range(k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        positive_feedback = set(positive_feedback)\n",
    "        negative_feedback = set(negative_feedback)\n",
    "        ans = []\n",
    "        for r, i in zip(report, student_id):\n",
    "            s = 0\n",
    "            for w in r.split():\n",
    "                if w in positive_feedback: s += 3\n",
    "                elif w in negative_feedback: s -= 1\n",
    "            ans.append([-s, i])\n",
    "        ans.sort()\n",
    "        return [x[1] for x in ans[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, zm: List[str], fm: List[str], r: List[str], ids: List[int], k: int) -> List[int]:\n",
    "        zm=set(zm)\n",
    "        fm=set(fm)\n",
    "        arr=[]\n",
    "        for word,i in zip(r,ids):\n",
    "            cnt=0\n",
    "            for w in word.split():\n",
    "                if w in zm:\n",
    "                    cnt+=3\n",
    "                if w in fm:\n",
    "                    cnt-=1\n",
    "            arr.append([i,cnt])\n",
    "        arr.sort(key=lambda x:(-x[1],x[0]))\n",
    "        res=[]\n",
    "        for i in range(k):\n",
    "            res.append(arr[i][0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        mx = -inf\n",
    "        positive_feedback = set(positive_feedback)\n",
    "        negative_feedback = set(negative_feedback)   \n",
    "        ans = []     \n",
    "        for idx, r in enumerate(report):\n",
    "            s = r.split()\n",
    "            score = 0\n",
    "            for item in s:\n",
    "                if item in positive_feedback:\n",
    "                    score+=3\n",
    "                elif item in negative_feedback:\n",
    "                    score-=1\n",
    "            ans.append([-score, student_id[idx]])\n",
    "        ans.sort()\n",
    "        return [item[1] for item in ans[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        p, n = set(positive_feedback), set(negative_feedback)\n",
    "        res = []\n",
    "        for rp, id in zip(report, student_id):\n",
    "            r = rp.split()\n",
    "            score = 0\n",
    "            for s in r:\n",
    "                if s in p:\n",
    "                    score += 3\n",
    "                elif s in n:\n",
    "                    score -= 1\n",
    "            res.append((-score, id))\n",
    "        res.sort()\n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            ans.append(res[i][1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        pri_que = []\n",
    "        pos_set = set(positive_feedback)\n",
    "        neg_set = set(negative_feedback)\n",
    "        for index in range(len(student_id)):\n",
    "            s_score = self.calscore(report[index], pos_set, neg_set)\n",
    "            s_id = student_id[index]\n",
    "            heapq.heappush(pri_que, (s_score, s_id))\n",
    "        arr = heapq.nlargest(k, pri_que, key = lambda x:(x[0], -x[1]))\n",
    "        return [arr[i][1] for i in range(k)]\n",
    "\n",
    "    def calscore(self, str: string, positive_feedback: List, negative_feedback:List) -> int:\n",
    "        res = 0\n",
    "        arr = str.split()\n",
    "        for val in arr:\n",
    "            if val in positive_feedback:\n",
    "                res += 3\n",
    "            if val in negative_feedback:\n",
    "                res -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        \n",
    "\n",
    "        res = defaultdict(list)\n",
    "        score = defaultdict(int)\n",
    "        for w in positive_feedback:\n",
    "            score[w]=3\n",
    "        for w in negative_feedback:\n",
    "            score[w]=-1\n",
    "        for r, i in zip(report, student_id):\n",
    "            words = r.strip().split(' ')\n",
    "            # print(words)\n",
    "            cnt = sum(score[w] for w in words)\n",
    "            res[cnt].append(i)\n",
    "            # out.append((i, cnt))\n",
    "            \n",
    "        sres = sorted(res.items(), key=lambda x: x[0], reverse=True)\n",
    "        \n",
    "        out = []\n",
    "        cnt = 0\n",
    "        for j, v in sres:\n",
    "            v.sort()\n",
    "            out.extend(v)\n",
    "            # cnt+=len(v)\n",
    "            # if cnt>k:\n",
    "            #     break  \n",
    "\n",
    "        return [out[i] for i in range(k)]\n",
    "        \n",
    "#         res = sorted(out, key=lambda x: x[1], reverse=True)\n",
    "#         # print(res)\n",
    "#         output = []\n",
    "#         for i in range(k):\n",
    "#             output.append(res[i][0])\n",
    "#         return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        h = {}\n",
    "        for positive in positive_feedback:\n",
    "            h[positive] = 1\n",
    "        for negative in negative_feedback:\n",
    "            h[negative] = 0\n",
    "        for i, v in enumerate(report):\n",
    "            score = 0\n",
    "            words = v.split(' ')\n",
    "            for word in words:\n",
    "                if word not in h:\n",
    "                    continue\n",
    "                if h[word] == 1:\n",
    "                    score += 3\n",
    "                if h[word] == 0:\n",
    "                    score -= 1\n",
    "            report[i] = score\n",
    "        data = list(zip(report, student_id))\n",
    "        data.sort(key=lambda x:(-x[0], x[1]))\n",
    "        res = []\n",
    "        i = 0\n",
    "        while k:\n",
    "            res.append(data[i][1])\n",
    "            k-=1\n",
    "            i+=1\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        pos = set(positive_feedback)\n",
    "        neg = set(negative_feedback)\n",
    "        \n",
    "        re = []\n",
    "        for sx in report:\n",
    "            cur = 0\n",
    "            for s in sx.split(' '):\n",
    "                if s in pos:\n",
    "                    cur += 3\n",
    "                elif s in neg:\n",
    "                    cur -= 1\n",
    "            re.append(cur)\n",
    "\n",
    "        idxs = [i for i in range(len(student_id))]\n",
    "        idxs.sort(key = lambda i: (-re[i], student_id[i]))\n",
    "        \n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            res.append(student_id[idxs[i]])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        sp=set(positive_feedback)\n",
    "        sn=set(negative_feedback)\n",
    "        \n",
    "        kk=[]\n",
    "        n=len(report)\n",
    "        for i in range(n):\n",
    "            score=0\n",
    "            feedb=report[i].split()\n",
    "            for s in feedb:\n",
    "                if s in sp:score+=3\n",
    "                if s in sn:score-=1\n",
    "            kk.append((score,-student_id[i]))\n",
    "        kk.sort(reverse=True)\n",
    "        \n",
    "        ans=[]\n",
    "        for i in range(k):\n",
    "            ans.append(-kk[i][1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        n = len(report)\n",
    "        positive_feedback = set(positive_feedback)\n",
    "        negative_feedback = set(negative_feedback)\n",
    "        \n",
    "        for i in range(n):\n",
    "            report[i] = -sum([3 if s in positive_feedback else (-1 if s in negative_feedback else 0) for s in report[i].split(\" \")])\n",
    "        \n",
    "        report = list(zip(report, student_id))\n",
    "\n",
    "        report.sort()\n",
    "        return [i[1] for i in report[:k]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        # 统计每个学生对应的分数\n",
    "        # 从最小堆里拿出前k个学生\n",
    "        # 按照id升序排序\n",
    "        dic = defaultdict(int)  # id: score\n",
    "        positive_feedback = set(positive_feedback)\n",
    "        negative_feedback = set(negative_feedback)\n",
    "        for repo, id in zip(report, student_id):\n",
    "            for word in repo.split():\n",
    "                dic[id] += 0\n",
    "                if word in positive_feedback:\n",
    "                    dic[id] += 3\n",
    "                elif word in negative_feedback:\n",
    "                    dic[id] -= 1\n",
    "        heap = []\n",
    "        for id, score in dic.items():\n",
    "            heappush(heap, (score, -id))  # 若分数相同, 优先popid大的\n",
    "            if len(heap) > k:\n",
    "                heappop(heap)\n",
    "        heap.sort(key=lambda x: (-x[0], -x[1]))\n",
    "        return [-id for _, id in heap]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str],\n",
    "                    student_id: List[int], k: int) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param positive_feedback:\n",
    "        :param negative_feedback:\n",
    "        :param report:\n",
    "        :param student_id:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        s1 = set(positive_feedback)\n",
    "        s2 = set(negative_feedback)\n",
    "        m1 = {}\n",
    "        for k2, v in enumerate(report):\n",
    "            v1, v2 = 0, 0\n",
    "            for j in v.split():\n",
    "                if j in s1:\n",
    "                    v1 += 3\n",
    "                if j in s2:\n",
    "                    v2 -= 1\n",
    "            m1[k2] = (v1, v2)\n",
    "\n",
    "        m2 = {}\n",
    "        for i in m1:\n",
    "            ans1 = m1[i][0] + m1[i][1]\n",
    "            m2[i] = (ans1, student_id[i])\n",
    "\n",
    "        ll = [(i, m2[i]) for i in m2]\n",
    "        ll.sort(key=lambda x: (-x[1][0], x[1][1]))\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "\n",
    "            res.append(ll[i][1][1])\n",
    "        return res\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.topStudents( positive_feedback = [\"smart\",\"brilliant\",\"studious\"], negative_feedback = [\"not\"], report = [\"this student is not studious\",\"the student is smart\"], student_id = [1,2], k = 2\n",
    "\n",
    "      ))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        positive_feedback = set(positive_feedback)\n",
    "        negative_feedback = set(negative_feedback)\n",
    "        for i, feedback in enumerate(report):\n",
    "            score = 0\n",
    "            words = feedback.split(' ')\n",
    "            for word in words:\n",
    "                if word in positive_feedback:\n",
    "                    score += 3\n",
    "                if word in negative_feedback:\n",
    "                    score -= 1\n",
    "            report[i] = (score, student_id[i])\n",
    "        report.sort(key=lambda x:(x[0], -x[1]), reverse=True)\n",
    "        return [report[i][1] for i in range(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        score=[]\n",
    "        pos =set(positive_feedback)\n",
    "        ne=set(negative_feedback)\n",
    "        for re in report:\n",
    "            temp=0\n",
    "            tt=re.split(' ')\n",
    "            for ss in tt:\n",
    "                if ss in pos:\n",
    "                     temp+=3\n",
    "                if ss in ne:\n",
    "                     temp-=1\n",
    "            score.append(temp)\n",
    "        ans=list(zip(score,student_id))\n",
    "        ans.sort(key=lambda x:(-x[0],x[1]))\n",
    "        return [s[1] for s in ans[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class StudentItem:\n",
    "        def __init__(self, id, score):\n",
    "            self.id = id\n",
    "            self.score = score\n",
    "        def __lt__(self, other):\n",
    "            if self.score < other.score:\n",
    "                return True \n",
    "            if self.score > other.score:\n",
    "                return False\n",
    "            return self.id > other.id\n",
    "\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        n = len(student_id)\n",
    "        pq = []\n",
    "        heapq.heapify(pq)\n",
    "        \n",
    "        ps = set(positive_feedback)\n",
    "        ns = set(negative_feedback)\n",
    "\n",
    "        ans = [[student_id[i], 0] for i in range(n)]\n",
    "        for i in range(n):\n",
    "            score = 0\n",
    "            words = report[i].split()\n",
    "            for word in words:\n",
    "                if word in ps:\n",
    "                    score += 3\n",
    "                    continue\n",
    "                if word in ns:\n",
    "                    score -= 1\n",
    "            if len(pq) == k:\n",
    "                heapq.heappushpop(pq, self.StudentItem(student_id[i], score))    \n",
    "            else:\n",
    "                heapq.heappush(pq, self.StudentItem(student_id[i], score))    \n",
    "\n",
    "        return [student_item.id for student_item in heapq.nlargest(k, pq)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        positive_feedback = set(positive_feedback)\n",
    "        negative_feedback = set(negative_feedback)\n",
    "        \n",
    "        n = len(student_id)\n",
    "\n",
    "        score_heap = []\n",
    "        for i in range(n):\n",
    "            report_list = report[i].split(\" \")\n",
    "            cur_score = 0\n",
    "            for word in report_list:\n",
    "                if word in positive_feedback:\n",
    "                    cur_score += 3\n",
    "                elif word in negative_feedback:\n",
    "                    cur_score -= 1\n",
    "\n",
    "            if len(score_heap) < k:\n",
    "                heapq.heappush(score_heap, [cur_score, -student_id[i]])\n",
    "            elif score_heap and (score_heap[0][0] < cur_score or (score_heap[0][0] == cur_score and -score_heap[0][1] > student_id[i])):\n",
    "                heapq.heappop(score_heap)\n",
    "                heapq.heappush(score_heap, [cur_score, -student_id[i]])\n",
    "        \n",
    "        print(score_heap)\n",
    "        ans = []\n",
    "        while score_heap:\n",
    "            ans.append(-heapq.heappop(score_heap)[1])\n",
    "        \n",
    "        ans = [ans[i] for i in range(len(ans)-1, -1, -1)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        scores={}\n",
    "        positive_feedback=set(positive_feedback)\n",
    "        negative_feedback=set(negative_feedback)\n",
    "        for i in range(len(student_id)):\n",
    "            score=0\n",
    "            for j in report[i].split(' '):\n",
    "                if j in positive_feedback:\n",
    "                    score+=3\n",
    "                if j in negative_feedback:\n",
    "                    score-=1\n",
    "            if score not in scores.keys():\n",
    "                scores[score]=[student_id[i]]\n",
    "            else:\n",
    "                scores[score].append(student_id[i])\n",
    "        res=[]\n",
    "        for i in sorted([*scores]):\n",
    "            res=sorted(scores[i])+res\n",
    "        return res[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        # 暴力计算法\n",
    "        scores = []\n",
    "        positive_set = set(positive_feedback)\n",
    "        negative_set = set(negative_feedback)\n",
    "        student_scores = defaultdict(list)\n",
    "        for i, r in enumerate(report):\n",
    "            score = 0\n",
    "            all_words = r.split(' ')\n",
    "            for word in all_words:\n",
    "                if word in positive_set:\n",
    "                    score += 3\n",
    "                elif word in negative_set:\n",
    "                    score -= 1\n",
    "            student_scores[score].append(student_id[i])\n",
    "        scores = list(student_scores.keys())\n",
    "        scores.sort(reverse=True)\n",
    "        top_scores = scores[:k]\n",
    "        top_ids = []\n",
    "        for score in top_scores:\n",
    "            ids = student_scores[score]\n",
    "            ids.sort()\n",
    "            top_ids.extend(ids)\n",
    "        return top_ids[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        scores = [0 for _ in student_id]\n",
    "        words = {}\n",
    "        for w in positive_feedback:\n",
    "            words[w] = 3\n",
    "        for w in negative_feedback:\n",
    "            words[w] = -1\n",
    "        \n",
    "        for i in range(len(student_id)):\n",
    "            s = report[i]\n",
    "            score = sum(words.get(w, 0)for w in s.split())\n",
    "            scores[i] = score\n",
    "        for i in range(k):\n",
    "            idx = i\n",
    "            for j in range(i+1, len(student_id)):\n",
    "                if scores[j] > scores[idx] or scores[j] == scores[idx] and student_id[j]<student_id[idx]:\n",
    "                    idx = j \n",
    "            if idx != i:\n",
    "                student_id[i], student_id[idx] = student_id[idx], student_id[i]\n",
    "                scores[i], scores[idx] = scores[idx], scores[i]\n",
    "        return student_id[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        n = len(report)\n",
    "        scores = {}\n",
    "        top_student_ids = []\n",
    "        words = {}\n",
    "        words.update({negative: -1 for negative in negative_feedback})\n",
    "        words.update({positive: 3 for positive in positive_feedback})\n",
    "\n",
    "        for comment, student in zip(report, student_id):\n",
    "            score = 0\n",
    "            for word in comment.split(\" \"):\n",
    "                score += words.get(word, 0)\n",
    "            if score not in scores:\n",
    "                scores[score] = [student]\n",
    "            else:\n",
    "                scores[score].append(student)\n",
    "        scores_list = sorted(scores.keys(), reverse = True)\n",
    "        for score in scores_list:\n",
    "            student_count = len(scores[score])\n",
    "            if k >= student_count:\n",
    "                k -= student_count\n",
    "                top_student_ids += sorted(scores[score])\n",
    "            else:\n",
    "                top_student_ids += sorted(scores[score])[:k]\n",
    "                break\n",
    "        return top_student_ids\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "\n",
    "        word_scores = {}\n",
    "        for w in positive_feedback:\n",
    "            word_scores[w] = 3\n",
    "        for w in negative_feedback:\n",
    "            word_scores[w] = -1\n",
    "\n",
    "        total_scores = []\n",
    "        for s, i in zip(report, student_id):\n",
    "            score = sum(word_scores.get(w, 0) for w in s.split())\n",
    "            total_scores.append([-score, i])\n",
    "        \n",
    "        total_scores.sort()\n",
    "        return [i for v,i in total_scores[:k]]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        sdict={}\n",
    "        for word in positive_feedback:\n",
    "            sdict[word]=3\n",
    "        for word in negative_feedback:\n",
    "            sdict[word]=-1\n",
    "        slist=[]\n",
    "        for i,s in zip(student_id,report):\n",
    "            score=sum(sdict.get(word,0) for word in s.split())\n",
    "            slist.append([score,-i])\n",
    "        min_heap=[]\n",
    "        for x in slist[:k]:\n",
    "            heapq.heappush(min_heap,x)\n",
    "        for x in slist[k:]:\n",
    "            if x>min_heap[0]:\n",
    "                heapq.heappop(min_heap)\n",
    "                heapq.heappush(min_heap,x)\n",
    "        min_heap.sort(reverse=True)\n",
    "        return [-x[1] for x in min_heap]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        words = {}\n",
    "        for w in positive_feedback:\n",
    "            words[w] = 3\n",
    "        for w in negative_feedback:\n",
    "            words[w] = -1\n",
    "        scores = []\n",
    "        for s, i in zip(report, student_id):\n",
    "            score = sum(words.get(w, 0) for w in s.split())\n",
    "            scores.append([-score, i])\n",
    "        scores.sort()\n",
    "        return [i for v, i in scores[:k]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        positive_feedback, negative_feedback = set(positive_feedback), set(negative_feedback)\n",
    "        arr = []\n",
    "        for r, sid in zip(report, student_id):\n",
    "            r, score = r.split(), 0\n",
    "            for sub in r:\n",
    "                if sub in positive_feedback:\n",
    "                    score += 3\n",
    "                elif sub in negative_feedback:\n",
    "                    score -= 1\n",
    "            if len(arr) < k:\n",
    "                heappush(arr, [score, -sid])\n",
    "            else:\n",
    "                heappushpop(arr, [score, -sid])\n",
    "\n",
    "        ans = []\n",
    "        while arr:\n",
    "            ans.append(-heappop(arr)[1])\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def topStudents(self, positive_feedback, negative_feedback, report, student_id, k):\n",
    "        words = {}\n",
    "        for w in positive_feedback:\n",
    "            words[w] = 3\n",
    "        for w in negative_feedback:\n",
    "            words[w] = -1\n",
    "        A = []\n",
    "        for s, i in zip(report, student_id):\n",
    "            score = sum(words.get(w, 0)for w in s.split())\n",
    "            A.append([-score, i])\n",
    "        A.sort()\n",
    "        return [i for v,i in A[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        words = {}\n",
    "        for w in positive_feedback:\n",
    "            words[w] = 3\n",
    "        for w in negative_feedback:\n",
    "            words[w] = -1\n",
    "        A = []\n",
    "        for s, i in zip(report, student_id):\n",
    "            score = sum(words.get(w, 0)for w in s.split())\n",
    "            A.append([-score, i])\n",
    "        A.sort()\n",
    "        return [i for v,i in A[:k]]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback, negative_feedback, report, student_id, k):\n",
    "        d = {}\n",
    "        for positive in positive_feedback:\n",
    "            d[positive] = 3\n",
    "        for negative in negative_feedback:\n",
    "            d[negative] = -1\n",
    "\n",
    "        k_list = []\n",
    "        for i in range(len(report)):\n",
    "            reward = sum(d[msg] if msg in d.keys() else 0 for msg in report[i].split())\n",
    "            k_list.append((-reward, student_id[i]))\n",
    "\n",
    "        k_list.sort()\n",
    "        return [st_id for (_, st_id) in k_list[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def topStudents(self, positive_feedback, negative_feedback, report, student_id, k):\n",
    "        words = {}\n",
    "        for w in positive_feedback:\n",
    "            words[w] = 3\n",
    "        for w in negative_feedback:\n",
    "            words[w] = -1\n",
    "        A = []\n",
    "        for s, i in zip(report, student_id):\n",
    "            score = sum(words.get(w, 0)for w in s.split())\n",
    "            A.append([-score, i])\n",
    "        A.sort()\n",
    "        return [i for v,i in A[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def topStudents(self, positive_feedback, negative_feedback, report, student_id, k):\n",
    "        words = {}\n",
    "        for w in positive_feedback:\n",
    "            words[w] = 3\n",
    "        for w in negative_feedback:\n",
    "            words[w] = -1\n",
    "        A = []\n",
    "        for s, i in zip(report, student_id):\n",
    "            score = sum(words.get(w, 0)for w in s.split())\n",
    "            A.append([-score, i])\n",
    "        A.sort()\n",
    "        return [i for v,i in A[:k]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        positive_set = set(positive_feedback)\n",
    "        negative_set = set(negative_feedback)\n",
    "\n",
    "        # 初始化学生分数字典\n",
    "        scores = {id: 0 for id in student_id}\n",
    "\n",
    "        # 遍历每个学生的评语\n",
    "        for id, text in zip(student_id, report):\n",
    "            # 分割每条评语并统计分数\n",
    "            words = text.split()\n",
    "            for word in words:\n",
    "                if word in positive_set:\n",
    "                    scores[id] += 3\n",
    "                elif word in negative_set:\n",
    "                    scores[id] -= 1\n",
    "\n",
    "        # 使用优先队列找出得分最高的 k 名学生\n",
    "        priority_queue = []\n",
    "        for id, score in scores.items():\n",
    "            # 将得分作为负数加入堆以建立最大堆\n",
    "            heapq.heappush(priority_queue, (-score, id))\n",
    "\n",
    "        # 取出得分最高的 k 名学生\n",
    "        top_students = []\n",
    "        while k > 0 and priority_queue:\n",
    "            score, id = heapq.heappop(priority_queue)\n",
    "            top_students.append(id)  # 直接添加学生 ID 到列表\n",
    "            k -= 1\n",
    "\n",
    "        # heapq 默认是最小堆，但我们通过添加负分数来模拟最大堆\n",
    "        # 无需反转，因为我们是按得分高到低取出的\n",
    "        return top_students\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def topStudents(self, positive_feedback, negative_feedback, report, student_id, k):\n",
    "        words = {}\n",
    "        for w in positive_feedback:\n",
    "            words[w] = 3\n",
    "        for w in negative_feedback:\n",
    "            words[w] = -1\n",
    "        A = []\n",
    "        for s, i in zip(report, student_id):\n",
    "            score = sum(words.get(w, 0)for w in s.split())\n",
    "            A.append([-score, i])\n",
    "        A.sort()\n",
    "        return [i for v,i in A[:k]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        positive_feedback = set(positive_feedback)\n",
    "        negative_feedback = set(negative_feedback)\n",
    "        cnt = defaultdict(int)\n",
    "        for (r, s) in zip(report, student_id):\n",
    "            cnt[s] = 0\n",
    "            tmp = r.split()\n",
    "            for w in tmp:\n",
    "                if w in positive_feedback:\n",
    "                    cnt[s] += 3\n",
    "                elif w in negative_feedback:\n",
    "                    cnt[s] -= 1\n",
    "        return sorted(cnt.keys(), key=lambda x: (-cnt[x], x))[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def topStudents(self, positive_feedback, negative_feedback, report, student_id, k):\n",
    "        words = {}\n",
    "        for w in positive_feedback:\n",
    "            words[w] = 3\n",
    "        for w in negative_feedback:\n",
    "            words[w] = -1\n",
    "        A = []\n",
    "        for s, i in zip(report, student_id):\n",
    "            score = sum(words.get(w, 0)for w in s.split())\n",
    "            A.append([-score, i])\n",
    "        A.sort()\n",
    "        return [i for v,i in A[:k]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback, negative_feedback, report, student_id, k):\n",
    "        d = {}\n",
    "        for positive in positive_feedback:\n",
    "            d[positive] = 3\n",
    "        for negative in negative_feedback:\n",
    "            d[negative] = -1\n",
    "\n",
    "        k_list = []\n",
    "        for i in range(len(report)):\n",
    "            reward = sum(d.get(msg, 0) for msg in report[i].split())\n",
    "            k_list.append((-reward, student_id[i]))\n",
    "\n",
    "        k_list.sort()\n",
    "        return [st_id for (_, st_id) in k_list[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        positive_feedback = set(positive_feedback)\n",
    "        negative_feedback = set(negative_feedback)\n",
    "    \n",
    "        @cache\n",
    "        def score(line):\n",
    "            ans = 0\n",
    "            for w in line.split():\n",
    "                if w in positive_feedback:\n",
    "                    ans += 3\n",
    "                elif w in negative_feedback:\n",
    "                    ans -= 1\n",
    "            return ans\n",
    "\n",
    "        rank = sorted(range(len(student_id)), key=lambda i:(-score(report[i]), student_id[i]))\n",
    "        return [student_id[rank[i]] for i in range(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        dic = {}\n",
    "        for i in positive_feedback:\n",
    "            dic[i] = 3\n",
    "        for i in negative_feedback:\n",
    "            dic[i] = -1\n",
    "        \n",
    "        scores = []\n",
    "\n",
    "        for r, s in zip(report, student_id):\n",
    "            scores.append((-sum(dic.get(w,0) for w in r.split()), s))\n",
    "        scores.sort()\n",
    "        return [s[1] for s in scores[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        positive_feedback=set(positive_feedback)\n",
    "        negative_feedback=set(negative_feedback)\n",
    "        def get_score(rep):\n",
    "            ws=rep.split(' ')\n",
    "            s=0\n",
    "            for w in ws:\n",
    "                if w in positive_feedback:\n",
    "                    s+=3\n",
    "                elif w in negative_feedback:\n",
    "                    s-=1\n",
    "            return s\n",
    "        n=len(student_id)\n",
    "        st=[(-get_score(report[i]),student_id[i]) for i in range(n)]\n",
    "        st.sort()\n",
    "        return [i for s,i in st[:k]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        que = []\n",
    "        pos = Counter(positive_feedback)\n",
    "        neg = Counter(negative_feedback)\n",
    "        n = len(student_id)\n",
    "        for i in range(n):\n",
    "            score = 0\n",
    "            for s in report[i].split():\n",
    "                if pos[s] > 0:\n",
    "                    score += 3\n",
    "                elif neg[s] > 0:\n",
    "                    score -= 1\n",
    "            heappush(que, (-score, student_id[i]))\n",
    "        res = []\n",
    "        while len(res) < k:\n",
    "            score, i = heappop(que)\n",
    "            res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        '''\n",
    "        哈希表：实现O(1)复杂度的查找\n",
    "        '''\n",
    "        # 记录每个评价对应的分数值\n",
    "        rec = {}\n",
    "        for w in positive_feedback:\n",
    "            rec[w] = 3\n",
    "        for w in negative_feedback:\n",
    "            rec[w] = -1\n",
    "\n",
    "        # 计算每个学生对应的分数\n",
    "        rst = []\n",
    "        for rep, id_ in zip(report, student_id):\n",
    "            tmp_score = sum([rec.get(i, 0) for i in rep.split()])\n",
    "            rst.append(\n",
    "                (tmp_score, id_)\n",
    "            )\n",
    "\n",
    "        rst.sort(key = lambda x: (x[0], -x[1]), reverse = True)\n",
    "        return [i[1] for i in rst[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        words = {}\n",
    "        for w in positive_feedback:\n",
    "            words[w] = 3\n",
    "        for w in negative_feedback:\n",
    "            words[w] = -1\n",
    "        res = []\n",
    "        for s,i in zip(report,student_id):\n",
    "            score = sum(words.get(w,0) for w in s.split())\n",
    "            res.append((score,i))\n",
    "        print(res)\n",
    "        res.sort(key=lambda x:(-x[0],x[1]))\n",
    "        return [r[1] for r in res[:k]]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(\n",
    "        self,\n",
    "        positive_feedback: List[str],\n",
    "        negative_feedback: List[str],\n",
    "        report: List[str],\n",
    "        student_id: List[int],\n",
    "        k: int,\n",
    "    ) -> List[int]:\n",
    "        ps = set(positive_feedback)\n",
    "        ns = set(negative_feedback)\n",
    "        arr = []\n",
    "        for sid, r in zip(student_id, report):\n",
    "            t = 0\n",
    "            for w in r.split():\n",
    "                if w in ps:\n",
    "                    t += 3\n",
    "                elif w in ns:\n",
    "                    t -= 1\n",
    "            arr.append((t, sid))\n",
    "        arr.sort(key=lambda x: (-x[0], x[1]))\n",
    "        return [v[1] for v in arr[:k]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        m = {}\n",
    "        for v in positive_feedback:\n",
    "            m[v] = 3\n",
    "        for v in negative_feedback:\n",
    "            m[v] = -1\n",
    "        n = len(report)\n",
    "        sd = []\n",
    "        for i in range(n):\n",
    "            sd.append((sum([m.get(v, 0) for v in report[i].split(' ')]), student_id[i]))\n",
    "        return [v for _,v in sorted(sd, key=lambda x:(-x[0], x[1]))[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(\n",
    "        self,\n",
    "        positive_feedback: List[str],\n",
    "        negative_feedback: List[str],\n",
    "        report: List[str],\n",
    "        student_id: List[int],\n",
    "        k: int,\n",
    "    ) -> List[int]:\n",
    "        ps = set(positive_feedback)\n",
    "        ns = set(negative_feedback)\n",
    "        arr = []\n",
    "        for sid, r in zip(student_id, report):\n",
    "            t = 0\n",
    "            for w in r.split():\n",
    "                if w in ps:\n",
    "                    t += 3\n",
    "                elif w in ns:\n",
    "                    t -= 1\n",
    "            arr.append((t, sid))\n",
    "        arr.sort(key=lambda x: (-x[0], x[1]))\n",
    "        return [v[1] for v in arr[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        positive_set = set(positive_feedback)\n",
    "        negative_set = set(negative_feedback)\n",
    "\n",
    "    # 初始化学生分数字典\n",
    "        scores = {id: 0 for id in student_id}\n",
    "\n",
    "    # 计算每个学生的分数\n",
    "        for i, text in enumerate(report):\n",
    "            words = text.split()\n",
    "            for word in words:\n",
    "                if word in positive_set:\n",
    "                    scores[student_id[i]] += 3\n",
    "                elif word in negative_set:\n",
    "                    scores[student_id[i]] -= 1\n",
    "\n",
    "    # 根据分数和ID排序学生\n",
    "        sorted_students = sorted(scores.items(), key=lambda item: (-item[1], item[0]))\n",
    "\n",
    "    # 获取前k个学生的ID\n",
    "        top_students = [student[0] for student in sorted_students[:k]]\n",
    "\n",
    "        return top_students\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(\n",
    "        self,\n",
    "        positive_feedback: List[str],\n",
    "        negative_feedback: List[str],\n",
    "        report: List[str],\n",
    "        student_id: List[int],\n",
    "        k: int,\n",
    "    ) -> List[int]:\n",
    "        ps = set(positive_feedback)\n",
    "        ns = set(negative_feedback)\n",
    "        arr = []\n",
    "        for sid, r in zip(student_id, report):\n",
    "            t = 0\n",
    "            for w in r.split():\n",
    "                if w in ps:\n",
    "                    t += 3\n",
    "                elif w in ns:\n",
    "                    t -= 1\n",
    "            arr.append((t, sid))\n",
    "        arr.sort(key=lambda x: (-x[0], x[1]))\n",
    "        return [v[1] for v in arr[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        positive_set = set(positive_feedback)\n",
    "        negative_set = set(negative_feedback)\n",
    "        rank = []\n",
    "        for sid, r in zip(student_id, report):\n",
    "            score = 0\n",
    "            for w in r.split():\n",
    "                if w in positive_set:\n",
    "                    score += 3\n",
    "                elif w in negative_set:\n",
    "                    score -= 1\n",
    "\n",
    "            rank.append((sid, score))\n",
    "\n",
    "        rank.sort(key = lambda x: (-x[1], x[0]))\n",
    "        return [stu[0] for stu in rank[:k]]\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        positive_feedback = set(positive_feedback)\n",
    "        negative_feedback = set(negative_feedback)\n",
    "        score = [0] * len(student_id)\n",
    "        for i in range(len(student_id)):\n",
    "            for word in report[i].split():\n",
    "                if word in positive_feedback: score[i] += 3\n",
    "                elif word in negative_feedback: score[i] -= 1\n",
    "        arr = list(zip(student_id, score))\n",
    "        # print(arr)\n",
    "        arr.sort(key = lambda x: (-x[1], x[0]))\n",
    "        return [arr[i][0] for i in range(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        positive_set=set(positive_feedback)\n",
    "        negative_set=set(negative_feedback)\n",
    "        # print(positive_set)\n",
    "        # print(negative_set)\n",
    "        ans=[]\n",
    "        for  i,word in zip(student_id, report):\n",
    "            list_word=list(word.split())\n",
    "            # print(list_word[3:])\n",
    "            res=0\n",
    "            for j in list_word:\n",
    "                if j in positive_set:\n",
    "                    res+=3\n",
    "                if j in negative_set:\n",
    "                    res+=-1\n",
    "            # print(ans)\n",
    "            ans.append((res,i))\n",
    "        # print(ans)\n",
    "        ans.sort(key=lambda x: (-x[0], x[1]))\n",
    "        return [v[1] for v in ans[:k]]\n",
    "\n",
    "             \n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        positive_set=set(positive_feedback)\n",
    "        negative_set=set(negative_feedback)\n",
    "        # print(positive_set)\n",
    "        # print(negative_set)\n",
    "        ans=[]\n",
    "        for  i,word in zip(student_id, report):\n",
    "            list_word=list(word.split())\n",
    "            # print(list_word[3:])\n",
    "            res=0\n",
    "            for j in list_word:\n",
    "                if j in positive_set:\n",
    "                    res+=3\n",
    "                if j in negative_set:\n",
    "                    res+=-1\n",
    "            # print(ans)\n",
    "            ans.append((res,i))\n",
    "        # print(ans)\n",
    "        ans.sort(key=lambda x: (-x[0], x[1]))\n",
    "        return [v[1] for v in ans[:k]]\n",
    "\n",
    "             \n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        d_pos,d_neg = {},{}\n",
    "        for pos in positive_feedback:\n",
    "            d_pos[pos] = 3\n",
    "        for neg in negative_feedback:\n",
    "            d_neg[neg] = -1\n",
    "        ans = []\n",
    "        for rep,sid in zip(report,student_id):\n",
    "            score = 0\n",
    "            words = rep.split(' ')\n",
    "            for w in words:\n",
    "                if w in d_pos:\n",
    "                    score += d_pos[w]\n",
    "                if w in d_neg:\n",
    "                    score += d_neg[w]\n",
    "            ans.append([score,sid])\n",
    "        ans.sort(key=lambda x : (0-x[0],x[1]))\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            res.append(ans[i][1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        positive_feedback = set(positive_feedback)\n",
    "        negative_feedback = set(negative_feedback)\n",
    "        arr = []\n",
    "        for sid, rpt in zip(student_id, report):\n",
    "            t = 0\n",
    "            for w in rpt.split():\n",
    "                if w in positive_feedback:\n",
    "                    t += 3\n",
    "                elif w in negative_feedback:\n",
    "                    t -= 1\n",
    "            arr.append((sid, t))\n",
    "        arr.sort(key=lambda x: (-x[1], x[0]))\n",
    "        return [x[0] for x in arr[:k]]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        pf = set(positive_feedback)\n",
    "        nf = set(negative_feedback)\n",
    "        res = []\n",
    "        #打包student_id和report\n",
    "        for id, rpt in zip(student_id, report):\n",
    "            score = 0\n",
    "            #把评语分割成数组\n",
    "            rp = rpt.split()\n",
    "            for r in rp:\n",
    "                if r in pf:\n",
    "                    score += 3\n",
    "                elif r in nf:\n",
    "                    score -= 1\n",
    "            res.append((id, score))\n",
    "        res.sort(key=lambda x: (-x[1],x[0]))\n",
    "        return [x[0] for x in res[:k]]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        l1 = set(positive_feedback)\n",
    "        l2 = set(negative_feedback)\n",
    "        l3 = []\n",
    "        target = []\n",
    "        n = 0\n",
    "        for i in range (len(report)):\n",
    "            x = 0\n",
    "            lx = list(report[i].split(\" \"))\n",
    "            for p in range (len(lx)):\n",
    "                if lx[p] in l1:\n",
    "                    x += 3\n",
    "                if lx[p] in l2:\n",
    "                    x -= 1\n",
    "            l3 += [[x, student_id[i]]]\n",
    "        l3 = sorted(l3, key = lambda x:(-x[0],x[1]) )\n",
    "        for i in range (k):\n",
    "            target.append(l3[i][1])\n",
    "        return target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        dic = {}\n",
    "        for w in positive_feedback:\n",
    "            dic[w]=3\n",
    "        for w in negative_feedback:\n",
    "            dic[w]=-1\n",
    "        for i in range(len(report)):\n",
    "            v=report[i].split()\n",
    "            score=0\n",
    "            for w in v:\n",
    "                score+=dic.get(w,0)\n",
    "            student_id[i]=(student_id[i],score)\n",
    "        student_id.sort(key=lambda x :(-x[1],x[0]))\n",
    "        res=[]\n",
    "        for i in range(k):\n",
    "            res.append(student_id[i][0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        l1 = set(positive_feedback)\n",
    "        l2 = set(negative_feedback)\n",
    "        l3 = []\n",
    "        target = []\n",
    "        n = 0\n",
    "        for i in range (len(report)):\n",
    "            x = 0\n",
    "            lx = list(report[i].split(\" \"))\n",
    "            for p in range (len(lx)):\n",
    "                if lx[p] in l1:\n",
    "                    x += 3\n",
    "                if lx[p] in l2:\n",
    "                    x -= 1\n",
    "            l3 += [[x, student_id[i]]]\n",
    "        l3 = sorted(l3, key = lambda x:(-x[0],x[1]) )\n",
    "        for i in range (k):\n",
    "            target.append(l3[i][1])\n",
    "        return target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        positive_feedback = set(positive_feedback)\n",
    "        negative_feedback = set(negative_feedback)\n",
    "        \n",
    "        def getScore(cur_report):\n",
    "            score = 0\n",
    "            words = cur_report.split()\n",
    "            for w in words:\n",
    "                if w in positive_feedback:\n",
    "                    score += 3\n",
    "                elif w in negative_feedback:\n",
    "                    score -= 1\n",
    "            return score\n",
    "                \n",
    "        \n",
    "        scores = list()\n",
    "        n = len(report)\n",
    "        for i in range(n):\n",
    "            cur_report = report[i]\n",
    "            cur_id = student_id[i]\n",
    "            score = getScore(cur_report)\n",
    "            scores.append((score, cur_id))\n",
    "        scores.sort(key=lambda item:(item[0], -item[1]), reverse=True)\n",
    "        return [item[1] for item in scores[:k]]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        from sortedcontainers import SortedList\n",
    "        positive_feedback = set(positive_feedback)\n",
    "        negative_feedback = set(negative_feedback)\n",
    "        ret = SortedList(key=lambda x: (-x[0], x[1]))\n",
    "        for s_index, r in enumerate(report):\n",
    "            cur = 0\n",
    "            words = r.split(' ')\n",
    "            for w in words:\n",
    "                if w in positive_feedback:\n",
    "                    cur += 3\n",
    "                elif w in negative_feedback:\n",
    "                    cur -= 1\n",
    "            ret.add([cur, student_id[s_index]])\n",
    "        return [ret[i][1] for i in range(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        pf = set(positive_feedback)\n",
    "        nf = set(negative_feedback)\n",
    "        for i in range(len(report)):\n",
    "            s = 0\n",
    "            for j in report[i].split(\" \"):\n",
    "                if j in pf:\n",
    "                    s += 3\n",
    "                elif j in nf:\n",
    "                    s -= 1\n",
    "            student_id[i] = [s, student_id[i]]\n",
    "        ans = sorted(student_id, key = lambda x:(x[0], -x[1]), reverse = True)\n",
    "        return [x[1] for x in ans][:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        from sortedcontainers import SortedList\n",
    "        positive_feedback = set(positive_feedback)\n",
    "        negative_feedback = set(negative_feedback)\n",
    "        ret = SortedList(key=lambda x: (-x[0], x[1]))\n",
    "        for s_index, r in enumerate(report):\n",
    "            cur = 0\n",
    "            words = r.split(' ')\n",
    "            for w in words:\n",
    "                if w in positive_feedback:\n",
    "                    cur += 3\n",
    "                elif w in negative_feedback:\n",
    "                    cur -= 1\n",
    "            ret.add([cur, student_id[s_index]])\n",
    "        return [ret[i][1] for i in range(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        positive_feedback = set(positive_feedback)\n",
    "        negative_feedback = set(negative_feedback)\n",
    "        def judge_score(report):\n",
    "            score = 0\n",
    "            for item in report.split():\n",
    "                if item in positive_feedback:\n",
    "                    score+=3\n",
    "                if item in negative_feedback:\n",
    "                    score-=1\n",
    "            return score\n",
    "\n",
    "        student = []\n",
    "        ls = len(student_id)\n",
    "        for i in range(ls):\n",
    "            student.append([student_id[i],judge_score(report[i])])\n",
    "            # student.append([judge_score(report[i]),-student_id[i]])\n",
    "\n",
    "        # heapq.heapify(student)\n",
    "        # ans = heapq.nlargest(student,k)\n",
    "        h = []\n",
    "        for idx,score in student:\n",
    "            heapq.heappush(h,stu(idx,score))\n",
    "        # print(h)\n",
    "        ans = heapq.nlargest(k,h)\n",
    "        ans = [item.id for item in ans]\n",
    "\n",
    "        # student.sort(key= lambda x :(-x[1],x[0]))\n",
    "        # ans = [student[i][0] for i in range(k)]\n",
    "        return ans\n",
    "\n",
    "class stu:\n",
    "    def __init__(self,idx,score):\n",
    "        self.id = idx\n",
    "        self.score = score\n",
    "    def __lt__(self,other):\n",
    "        if self.score<other.score:\n",
    "            return True\n",
    "        elif self.score==other.score:\n",
    "            if self.id>other.id:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str],\n",
    "                    student_id: List[int], k: int) -> List[int]:\n",
    "        pos = set(positive_feedback)\n",
    "        neg = set(negative_feedback)\n",
    "        n = len(report)\n",
    "        score = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            id = student_id[i]\n",
    "            score[id] = 0\n",
    "            for s in report[i].split():\n",
    "                if s in pos:\n",
    "                    score[id] += 3\n",
    "                elif s in neg:\n",
    "                    score[id] -= 1\n",
    "        l = [(i, sco) for i, sco in score.items()]\n",
    "        l.sort(key=lambda x: (-x[1], [x[0]]))\n",
    "        return [x[0] for x in l[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        scores = defaultdict(int)\n",
    "        for x in positive_feedback:\n",
    "            scores[x] = 3\n",
    "        for x in negative_feedback:\n",
    "            scores[x] = -1\n",
    "        nums= []\n",
    "        for idx, s in enumerate(report):\n",
    "            s = s.split()\n",
    "            score = 0\n",
    "            for item in s:\n",
    "                score += scores[item]\n",
    "            nums.append((-score, student_id[idx]))\n",
    "        nums.sort()\n",
    "        return [item[1] for item in nums[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        d = defaultdict(int)\n",
    "        for x in set(positive_feedback):\n",
    "            d[x] += 3\n",
    "        for y in set(negative_feedback):\n",
    "            d[y] -= 1\n",
    "        ans = defaultdict(int)\n",
    "        for x, y in zip(report, student_id):\n",
    "            words = x.split()\n",
    "            res = 0\n",
    "            for w in words:\n",
    "                if w in d:\n",
    "                    res += d[w]\n",
    "            ans[y] += res\n",
    "        tmp = list(ans.items())\n",
    "        tmp.sort(key=lambda x: (-x[1], x[0]))\n",
    "        return [x[0] for x in tmp[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        positive_set = set(positive_feedback)\n",
    "        negative_set = set(negative_feedback)\n",
    "\n",
    "        scores = []\n",
    "        for r in report:\n",
    "            score = 0\n",
    "            words = r.split(\" \")\n",
    "            for word in words:\n",
    "                if word in positive_set:\n",
    "                    score += 3\n",
    "                elif word in negative_set:\n",
    "                    score -= 1\n",
    "            scores.append(score)\n",
    "        \n",
    "        student_id, scores = zip(*sorted(zip(student_id, scores), key=lambda x: (-x[1], x[0])))\n",
    "        print(scores[:k])\n",
    "        return student_id[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left, bisect_right, insort_left, insort_right, insort, bisect\n",
    "from math import ceil, floor, pow, gcd, sqrt, log10, fabs, fmod, factorial, inf, pi, e\n",
    "from heapq import heapify, heapreplace, heappush, heappop, heappushpop, nlargest, nsmallest\n",
    "from collections import defaultdict, Counter, deque\n",
    "from itertools import permutations, combinations, combinations_with_replacement, accumulate, count, groupby, pairwise\n",
    "from queue import PriorityQueue, Queue, LifoQueue\n",
    "from functools import lru_cache, cache\n",
    "from typing import List, Optional\n",
    "import sys\n",
    "\n",
    "from sortedcontainers import SortedList, SortedDict, SortedSet\n",
    "\n",
    "sys.setrecursionlimit(10001000)\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "INFMIN = float('-inf')\n",
    "INFMAX = float('inf')\n",
    "PI = 3.141592653589793\n",
    "direc = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "direc8 = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]\n",
    "ALPS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n",
    "alps = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "\n",
    "def alp(i):\n",
    "    return chr(ord('a') + i % 26)  # i=0->'a', i=25->'z'\n",
    "\n",
    "\n",
    "def input():\n",
    "    return sys.stdin.readline().rstrip()\n",
    "\n",
    "\n",
    "def end(r=-1):\n",
    "    print(r)\n",
    "    1\n",
    "    exit()\n",
    "\n",
    "\n",
    "# --idea\n",
    "# -*- coding: utf-8 -*-\n",
    "# @Author  : hakusai\n",
    "# @Time    : 2023/10/11 08:32\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str],\n",
    "                    student_id: List[int], k: int) -> List[int]:\n",
    "        p = set(positive_feedback)\n",
    "        n = set(negative_feedback)\n",
    "        ans = []\n",
    "        for i, v in enumerate(report):\n",
    "            s = 0\n",
    "            for w in v.split(\" \"):\n",
    "                if w in p:\n",
    "                    s += 3\n",
    "                elif w in n:\n",
    "                    s -= 1\n",
    "            ans.append([s, student_id[i]])\n",
    "        ans.sort(key=lambda x: (-x[0], x[1]))\n",
    "        return [s1[1] for s1 in ans[:k]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        n = len(student_id)\n",
    "        words = collections.defaultdict(int)\n",
    "        for w in positive_feedback:\n",
    "            words[w] = 3\n",
    "        for w in negative_feedback:\n",
    "            words[w] = -1\n",
    "\n",
    "        ret = []\n",
    "        for s, i in zip(report, student_id):\n",
    "            score = sum(words[w] for w in s.split())\n",
    "            ret.append([-score, i])\n",
    "\n",
    "        return [i for v, i in sorted(ret)[:k]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        from functools import cmp_to_key\n",
    "        p = set(positive_feedback)\n",
    "        n = set(negative_feedback)\n",
    "        def cmp(a, b):\n",
    "            if a['s'] > b['s']:\n",
    "                return -1\n",
    "            elif a['s'] < b['s']:\n",
    "                return 1\n",
    "            else:\n",
    "                return a['id'] - b['id']\n",
    "        rank = []\n",
    "        for i in range(len(report)):\n",
    "            r = report[i].split(' ')\n",
    "            tmp = {}\n",
    "            tmp['id'] = student_id[i]\n",
    "            tmp['s'] = 0\n",
    "            for j in r:\n",
    "                if j in p:\n",
    "                    tmp['s'] += 3\n",
    "                elif j in n:\n",
    "                    tmp['s'] -= 1\n",
    "            rank.append(tmp)\n",
    "        rank = sorted(rank, key=cmp_to_key(cmp))\n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            ans.append(rank[i]['id'])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        reportSource = []\n",
    "        srtuple = []\n",
    "        map = defaultdict(int)\n",
    "        for i in positive_feedback:\n",
    "            map[i]=3\n",
    "        for i in negative_feedback:\n",
    "            map[i]=-1\n",
    "\n",
    "        for i in report:\n",
    "            reportSource.append(0)\n",
    "            for j in i.split(\" \"):\n",
    "                reportSource[-1]+=map[j]\n",
    "        \n",
    "        for i in range(len(student_id)):\n",
    "            srtuple.append((student_id[i],reportSource[i]))\n",
    "        srtuple.sort(key= lambda x :(-x[1],x[0]))\n",
    "        res = [0]*k\n",
    "        for i in range(k):\n",
    "            res[i] = srtuple[i][0]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        import heapq\n",
    "        score_rec = defaultdict(int)\n",
    "        for pos in positive_feedback:\n",
    "            score_rec[pos] = 3\n",
    "        for neg in negative_feedback:\n",
    "            score_rec[neg] = -1\n",
    "        \n",
    "        student_score = defaultdict(int)\n",
    "        n = len(report)\n",
    "        for i in range(n):\n",
    "            resp = report[i].split()\n",
    "            for r in resp:\n",
    "                student_score[student_id[i]] += score_rec[r]\n",
    "        \n",
    "        res = [[key, value] for key, value in student_score.items()]\n",
    "        res.sort(key = lambda x:x[0])\n",
    "        res.sort(key = lambda x:x[1], reverse = True)\n",
    "        ans = [res[i][0] for i in range(k)]\n",
    "        return ans\n",
    "        # for key, value in student_score.items():\n",
    "        #     heapq.heappush(res, (value, key))\n",
    "        #     if len(res) > k:\n",
    "        #         heapq.heappop(res)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        score = defaultdict(int)\n",
    "        for w in positive_feedback: score[w] = 3\n",
    "        for w in negative_feedback: score[w] = -1\n",
    "        a = sorted((-sum(score[w] for w in r.split()), i) for r, i in zip(report, student_id))\n",
    "        return [i for _, i in a[:k]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        sorce = defaultdict(int)\n",
    "        for w in positive_feedback:sorce[w] = 3\n",
    "        for w in negative_feedback:sorce[w] = -1\n",
    "        a = sorted((-sum(sorce[w] for w in r.split()),i) for r,i in zip(report,student_id))\n",
    "        return  [i for _,i in a[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        score=[]\n",
    "        dic=collections.defaultdict(int)\n",
    "        for word in negative_feedback:\n",
    "            dic[word]=-1\n",
    "        for word in positive_feedback:\n",
    "            dic[word]=3\n",
    "        for i in range(len(report)):\n",
    "            re=report[i].split()\n",
    "            s=0\n",
    "            for j in re:\n",
    "                s=s+dic[j]\n",
    "            score.append((-s,student_id[i]))\n",
    "\n",
    "        #print(score)\n",
    "        score.sort()\n",
    "        #print(score)\n",
    "\n",
    "        return list(list(zip(*score))[1])[0:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        dic = defaultdict(int)\n",
    "        for item in positive_feedback:\n",
    "            dic[item] = 3\n",
    "        for item in negative_feedback:\n",
    "            dic[item] = -1\n",
    "        res = []\n",
    "        for i in range(len((report))):\n",
    "            grade = 0\n",
    "            feedback = report[i].split(' ')\n",
    "            for feed in feedback:\n",
    "                grade += dic[feed]\n",
    "            res.append((student_id[i],grade))\n",
    "        res = sorted(res,key = lambda item:(-item[1],item[0]))\n",
    "        return [res[i][0] for i in range(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        score=[]\n",
    "        dic=collections.defaultdict(int)\n",
    "        for word in negative_feedback:\n",
    "            dic[word]=-1\n",
    "        for word in positive_feedback:\n",
    "            dic[word]=3\n",
    "        for i in range(len(report)):\n",
    "            re=report[i].split()\n",
    "            s=0\n",
    "            for j in re:\n",
    "                s=s+dic[j]\n",
    "            score.append((-s,student_id[i]))\n",
    "\n",
    "        #print(score)\n",
    "        score.sort()\n",
    "        #print(score)\n",
    "\n",
    "        return list(list(zip(*score))[1])[0:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        score=defaultdict(int)\n",
    "        for w in positive_feedback: score[w]=3\n",
    "        for w in negative_feedback: score[w]=-1\n",
    "\n",
    "        stu=[]\n",
    "        for r,i in zip(report,student_id):\n",
    "            s=0\n",
    "            for w in r.split():\n",
    "                s+=score[w]\n",
    "            stu.append((-s,i))\n",
    "        stu.sort()\n",
    "        return [i for _,i in stu[:k] ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        sorce = defaultdict(int)\n",
    "        for w in positive_feedback:sorce[w] = 3\n",
    "        for w in negative_feedback:sorce[w] = -1\n",
    "        a = sorted((-sum(sorce[w] for w in r.split()),i) for r,i in zip(report,student_id))\n",
    "        return  [i for _,i in a[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        scores = defaultdict(int)\n",
    "        for pf in positive_feedback:\n",
    "            scores[pf] = 3\n",
    "        for nf in negative_feedback:\n",
    "            scores[nf] = -1\n",
    "        students = []\n",
    "        for r, sid in zip(report, student_id):\n",
    "            total = 0\n",
    "            for w in r.split():\n",
    "                total += scores[w]\n",
    "            students.append((-total, sid))\n",
    "        students.sort()\n",
    "        return [i for _, i in students[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:\n",
    "        # 把feedback及其分数存到哈希表score中，对每个report按照空格分割，用score计算分数之和\n",
    "        # 最后按题目规则排序，取前k个studentId为答案\n",
    "        # 自定义排序模拟\n",
    "        score = defaultdict(int)\n",
    "        for w in positive_feedback: score[w] = 3\n",
    "        for w in negative_feedback: score[w] = -1\n",
    "        a = sorted((-sum(score[w] for w in r.split()), i) for r,i in zip(report, student_id))\n",
    "        return [i for _, i in a[:k]]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
